package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see     [1051. 高度检查器 - 力扣（LeetCode）](https://leetcode.cn/problems/height-checker/submissions/)
 * @since Created by work on 2022/6/13 22:35
 */
public class HeightChecker {

    /**
     * 暴力解法
     * @param heights
     * @return
     */
    public int heightChecker(int[] heights) {
        int len = heights.length;
        List<Integer> integerArrayList = new ArrayList<>(len);
        for (int i = 0; i < len; i++) {
            integerArrayList.add(heights[i]);
        }
        Collections.sort(integerArrayList);
        int result = 0;
        for (int i = 0; i < len; i++) {
            if (integerArrayList.get(i) != heights[i]) {
                result++;
            }
        }
        return result;
    }


    /**
     * 桶排序+利用数据限制
     * @param heights
     * @return
     */
    public int heightChecker2(int[] heights) {
        int len = heights.length;
        int result = 0;

        final int MAX_SIZE = 101;
        int[] book = new int[MAX_SIZE];
        for (int i = 0; i < len; i++) {
            book[heights[i]]++;
        }

        int tag = 0;
        for (int i = 0; i < MAX_SIZE; i++) {
            if (book[i] == 0) {
                continue;
            }
            while (book[i] > 0) {
                if (heights[tag++] != i) {
                    result++;
                }
                book[i]--;
            }
            if (tag == len) {
                break;
            }
        }


        return result;
    }
}
